// https://www.lintcode.com/problem/find-k-closest-elements/description

class Solution {
public:
    /**
     * @param A: an integer array
     * @param target: An integer
     * @param k: An integer
     * @return: an integer array
     */
    vector<int> kClosestNumbers(vector<int>& arr, int x, int k) {
        int n = arr.size();
        int begin = 0;
        int end = n - 1;
        vector<int> result;
        while (begin + 1 < end)
        {
            int mid = (end - begin) / 2 + begin;
            if (arr[mid] < x)
                begin = mid;
            else 
                end = mid;
        }
        // if (arr[begin] > x) //错的，begin和end另一边也可以取
        // {
        //     for (int i = 0; i < k; ++i)
        //     {
        //         result.push_back(arr[begin + i]);
        //     }
        //     return result;
        // }
        // if (arr[end] < x)
        // {
        //     for (int i = 0; i < k; ++i)
        //     {
        //         result.push_back(arr[end - i]);
        //     }
        //     return result;
        // }
        int size = 0;
        while (size < k)
        {
            if ((begin >= 0 && abs(x - arr[begin]) <= abs(arr[end] - x)) || end >= n)
            {
                result.push_back(arr[begin]);
                begin--;
            } 
            else
            {
                result.push_back(arr[end]);
                end++;
            }
            size++;
        }
        // while (size < k) 多余
        // {
        //     if (begin >= 0)
        //     {
        //         result.push_back(arr[begin]);
        //         begin--;
        //     } else
        //     {
        //         result.push_back(arr[end]);
        //         end++;
        //     }
        // }
        return result;
    }    
};